1. Field of the Invention
The present disclosure relates to compression and decompression techniques, especially to a dictionary-based compression method, a dictionary-based decompression method and a dictionary composing method.
2. Description of Related Art
There are a lot of digital data compression algorithms. Some of them lead to data distortion, but some of them are lossless. Among these algorithms, Lempel-Ziv is a well-known lossless compression algorithm. Many analogous algorithms are derived therefrom, and the main characteristic thereof is using dictionary and dictionary index to replace the original data. For instance, such algorithms may scan the original data, store the unique and repeated contents of the data (e.g., a single symbol or the combination of several symbols) in a dictionary and use a brief code to take the place of the unique contents so as to achieve the purpose of lossless data compression. However, most of the dictionary-based compression algorithms relate to a single-layer dictionary, which means that such algorithm executes dictionary-based compression by a fixed unit range.
In addition, in order to save the instruction set storage size of a micro controller unit (MCU) so as to reduce cost and/or to accelerate the transmission efficiency of an instruction set, it is common to compress the instruction set. Some instruction set compression techniques compress an instruction set and store it in a non-cache memory (e.g., a flash memory or a main DRAM). Such techniques then decompress the compressed instruction set when a cache memory with the instruction set is loaded. However, most of the current instruction set compression techniques (e.g., compression techniques utilizing Huffman Encoding) have at least one of the following problems: the non-constant or unpredictable time for decompression (,which makes it hard to estimate the operation efficiency) and the limited starting point of decompression (i.e., the start of a compressed instruction set or the start of a specific coded block) instead of any coded unit of a coded block (,which reduces the efficiency of decompression).
People who are interested in dictionary-based compression algorithms and instruction set compression techniques may refer to the following documents: Charles Lefurgy, Peter Bird, I-Cheng Chen, Trevor Mudge, “Improving Code Density Using Compression Techniques”, Proceedings of Micro-30, Dec. 1-3, 1997; Yoshihisa Mano, Yutaka Sato, “A Data Compression Scheme which Achieves Good Compression for Practical Use”, IEEE, 1991.